{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "#############in MLia chap14\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "from numpy import * \n",
    "from numpy import linalg as la\n",
    "#import svdRec\n",
    "\n",
    "import os \n",
    "os.chdir(\"/home/lab466/pythons/pyMLIA35/Ch14SVD\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def loadExData():\n",
    "    return [[0, 0, 0, 2, 2],\n",
    "            [0, 0, 0, 3, 3],\n",
    "            [0, 0, 0, 1, 1],\n",
    "            [1, 1, 1, 0, 0],\n",
    "            [2, 2, 2, 0, 0],\n",
    "            [5, 5, 5, 0, 0],\n",
    "            [1, 1, 1, 0, 0]]\n",
    "\n",
    "\n",
    "def loadExData2():\n",
    "    return [[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5],\n",
    "            [0, 0, 0, 3, 0, 4, 0, 0, 0, 0, 3],\n",
    "            [0, 0, 0, 0, 4, 0, 0, 1, 0, 4, 0],\n",
    "            [3, 3, 4, 0, 0, 0, 0, 2, 2, 0, 0],\n",
    "            [5, 4, 5, 0, 0, 0, 0, 5, 5, 0, 0],\n",
    "            [0, 0, 0, 0, 5, 0, 1, 0, 0, 5, 0],\n",
    "            [4, 3, 4, 0, 0, 0, 0, 5, 5, 0, 1],\n",
    "            [0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 4],\n",
    "            [0, 0, 0, 2, 0, 2, 5, 0, 0, 1, 2],\n",
    "            [0, 0, 0, 0, 5, 0, 0, 0, 0, 4, 0],\n",
    "            [1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#相似度1：欧式距离\n",
    "def ecludSim(inA,inB):\n",
    "    return 1.0/(1.0 + la.norm(inA - inB))\n",
    "#相似度2：威尔逊距离\n",
    "def pearsSim(inA,inB):\n",
    "    if len(inA) < 3 : return 1.0\n",
    "    return 0.5+0.5*corrcoef(inA, inB, rowvar = 0)[0][1]\n",
    "#相似度3：余弦\n",
    "def cosSim(inA,inB):\n",
    "    num = float(inA.T*inB)\n",
    "    denom = la.norm(inA)*la.norm(inB)\n",
    "    return 0.5 + 0.5 * (num / denom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#遍历 计算相似度\n",
    "def standEst(dataMat, user, simMeas, item):#数据矩阵、用户编号、相似度计算方法和物品编号\n",
    "    n = shape(dataMat)[1]\n",
    "    simTotal = 0.0;ratSimTotal = 0.0\n",
    "    for j in range(n):\n",
    "        userRating = dataMat[user, j]\n",
    "        if userRating == 0: continue\n",
    "        #寻找两个用户都做了评价的产品\n",
    "        overLap = nonzero(logical_and(dataMat[:, item].A > 0, dataMat[:, j].A > 0))[0]\n",
    "        if len(overLap) == 0:\n",
    "            similarity = 0\n",
    "        else:#存在两个用户都评价的产品 计算相似度\n",
    "            similarity = simMeas(dataMat[overLap, item], dataMat[overLap, j])\n",
    "        print ('the %d and %d similarity is: %f' % (item, j, similarity))\n",
    "        simTotal += similarity #计算每个用户对所有评价产品累计相似度\n",
    "        ratSimTotal += similarity * userRating  #根据评分计算比率\n",
    "    if simTotal == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return ratSimTotal / simTotal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#利用SVD\n",
    "def svdEst(dataMat, user, simMeas, item):\n",
    "    n = shape(dataMat)[1]\n",
    "    simTotal = 0.0;ratSimTotal = 0.0\n",
    "    U, Sigma, VT = la.svd(dataMat) #不同于stanEst函数，加入了SVD分解\n",
    "    Sig4 = mat(eye(4) * Sigma[:4])  # 建立对角矩阵\n",
    "    xformedItems = dataMat.T * U[:, :4] * Sig4.I #降维：变换到低维空间\n",
    "    #下面依然是计算相似度，给出归一化评分\n",
    "    for j in range(n):\n",
    "        userRating = dataMat[user, j]\n",
    "        if userRating == 0 or j == item: continue\n",
    "        similarity = simMeas(xformedItems[item, :].T, xformedItems[j, :].T)\n",
    "        print ('the %d and %d similarity is: %f' % (item, j, similarity))\n",
    "        simTotal += similarity\n",
    "        ratSimTotal += similarity * userRating\n",
    "    if simTotal == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return ratSimTotal / simTotal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def recommend(dataMat, user, N=3, simMeas=cosSim, estMethod=standEst):\n",
    "    unratedItems = nonzero(dataMat[user, :].A == 0)[1] #寻找用户未评价的产品\n",
    "    if len(unratedItems) == 0: return ('you rated everything')\n",
    "    itemScores = []\n",
    "    for item in unratedItems:\n",
    "        estimatedScore = estMethod(dataMat, user, simMeas, item)#基于相似度的评分\n",
    "        itemScores.append((item, estimatedScore))\n",
    "    return sorted(itemScores, key=lambda jj: jj[1], reverse=True)[:N]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#实例：SVD实现图像压缩\n",
    "\n",
    "#打印矩阵。由于矩阵包含了浮点数,因此必须定义浅色和深色。\n",
    "def printMat(inMat, thresh=0.8):\n",
    "    for i in range(32):\n",
    "        for k in range(32):\n",
    "            if float(inMat[i,k]) > thresh:\n",
    "                print (1,)\n",
    "            else: print (0,)\n",
    "        print ('')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#压缩\n",
    "def imgCompress(numSV=3, thresh=0.8):\n",
    "    myl = []\n",
    "    for line in open('0_5.txt').readlines():\n",
    "        newRow = []\n",
    "        for i in range(32):\n",
    "            newRow.append(int(line[i]))\n",
    "        myl.append(newRow)\n",
    "    myMat = mat(myl)\n",
    "    print (\"****original matrix******\")\n",
    "    #printMat(myMat, thresh)\n",
    "    U,Sigma,VT = la.svd(myMat) #SVD分解\n",
    "    SigRecon = mat(zeros((numSV, numSV))) #创建初始特征\n",
    "    for k in range(numSV):#构造对角矩阵\n",
    "        SigRecon[k,k] = Sigma[k]\n",
    "    reconMat = U[:,:numSV]*SigRecon*VT[:numSV,:]\n",
    "    print (\"****reconstructed matrix using %d singular values******\" % numSV)\n",
    "    #printMat(reconMat, thresh)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[-0.70710678, -0.70710678],\n",
       "       [-0.70710678,  0.70710678]])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "##P255 利用python实现SVD \n",
    "U,Sigma,VT=linalg.svd([[1, 1],[7, 7]])\n",
    "# \n",
    "U\n",
    "# \n",
    "Sigma\n",
    "# \n",
    "VT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([9.64365076e+00, 5.29150262e+00, 8.36478329e-16, 6.91811207e-17,\n",
       "       1.11917251e-33])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## P256 进行SVD分解\n",
    "#import svdRec\n",
    "Data=loadExData()\n",
    "U,Sigma,VT=linalg.svd(Data)\n",
    "Sigma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 4.47427211e-17,  1.57774942e-15,  2.08638397e-15,\n",
       "          2.00000000e+00,  2.00000000e+00],\n",
       "        [-7.56974048e-16,  5.27282824e-16,  2.29691224e-16,\n",
       "          3.00000000e+00,  3.00000000e+00],\n",
       "        [-2.27747782e-16,  1.76121044e-16,  5.16267387e-17,\n",
       "          1.00000000e+00,  1.00000000e+00],\n",
       "        [ 1.00000000e+00,  1.00000000e+00,  1.00000000e+00,\n",
       "          1.03851855e-16,  1.03851855e-16],\n",
       "        [ 2.00000000e+00,  2.00000000e+00,  2.00000000e+00,\n",
       "          2.07703709e-16,  2.07703709e-16],\n",
       "        [ 5.00000000e+00,  5.00000000e+00,  5.00000000e+00,\n",
       "         -6.69808260e-33, -5.02356195e-33],\n",
       "        [ 1.00000000e+00,  1.00000000e+00,  1.00000000e+00,\n",
       "          1.03851855e-16,  1.03851855e-16]])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#由于Sigma是以向量的形式存储，故需要将其转为矩阵，\n",
    "#利用numpy的diag函数，直接Sig3 = np.diag(Sigma)[:3,:3]即可，\n",
    "#diag将行向量转为矩阵，值放在对角线上,并取前面3行3列\n",
    "Sig3=mat([[Sigma[0], 0, 0],[0, Sigma[1], 0], [0, 0, Sigma[2]]])\n",
    "#重构原始矩阵\n",
    "U[:,:3]*Sig3*VT[:3,:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "## P259基于协同过滤的推荐引擎\n",
    "##reload(svdRec)\n",
    "\n",
    "## \n",
    "myMat=mat(loadExData())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## \n",
    "\n",
    "ecludSim(myMat[:,0], myMat[:,4])#第一行和第五行欧式距离\n",
    "ecludSim(myMat[:,0], myMat[:,0])#第一行和第一行欧式距离\n",
    "cosSim(myMat[:,0], myMat[:,4])#第一行和第五行cos距离\n",
    "cosSim(myMat[:,0], myMat[:,0])#第一行和第一行cos距离\n",
    "pearsSim(myMat[:,0], myMat[:,4])#第一行和第五行皮尔逊距离\n",
    "pearsSim(myMat[:,0], myMat[:,0])#第一行和第一行皮尔逊距离"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[4, 4, 0, 2, 2],\n",
       "        [4, 0, 0, 3, 3],\n",
       "        [4, 0, 0, 1, 1],\n",
       "        [1, 1, 1, 2, 0],\n",
       "        [2, 2, 2, 0, 0],\n",
       "        [5, 5, 5, 0, 0],\n",
       "        [1, 1, 1, 0, 0]])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## P260 示例：餐馆菜肴推荐引擎\n",
    "##reload(svdRec)\n",
    "## 调入原始矩阵\n",
    "myMat=mat(loadExData())\n",
    "##修改其中一些值 ，然后显示矩阵\n",
    "myMat[0,1]=myMat[0,0]=myMat[1,0]=myMat[2,0]=4\n",
    "myMat[3,3]=2\n",
    "myMat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the 1 and 0 similarity is: 1.000000\n",
      "the 1 and 3 similarity is: 0.928746\n",
      "the 1 and 4 similarity is: 1.000000\n",
      "the 2 and 0 similarity is: 1.000000\n",
      "the 2 and 3 similarity is: 1.000000\n",
      "the 2 and 4 similarity is: 0.000000\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(2, 2.5), (1, 2.0243290220056256)]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## 尝试默认的推荐\n",
    "recommend(myMat, 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the 1 and 0 similarity is: 1.000000\n",
      "the 1 and 3 similarity is: 0.309017\n",
      "the 1 and 4 similarity is: 0.333333\n",
      "the 2 and 0 similarity is: 1.000000\n",
      "the 2 and 3 similarity is: 0.500000\n",
      "the 2 and 4 similarity is: 0.000000\n",
      "the 1 and 0 similarity is: 1.000000\n",
      "the 1 and 3 similarity is: 1.000000\n",
      "the 1 and 4 similarity is: 1.000000\n",
      "the 2 and 0 similarity is: 1.000000\n",
      "the 2 and 3 similarity is: 1.000000\n",
      "the 2 and 4 similarity is: 0.000000\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(2, 2.5), (1, 2.0)]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## 利用其他的相似度来推荐\n",
    "recommend(myMat, 2, simMeas=ecludSim)\n",
    "recommend(myMat, 2, simMeas=pearsSim)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([15.77075346, 11.40670395, 11.03044558,  4.84639758,  3.09292055,\n",
       "        2.58097379,  1.00413543,  0.72817072,  0.43800353,  0.22082113,\n",
       "        0.07367823])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## P263 利用SVD提高推荐效果\n",
    "from numpy import linalg as la\n",
    "## 计算在奇异值的总能量，了解其到底需要多少维特征\n",
    "U,Sigma,VT=la.svd(mat(loadExData2()))\n",
    "## \n",
    "Sigma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "500.5002891275791"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## \n",
    "Sig2=Sigma**2\n",
    "## \n",
    "sum(Sig2)\n",
    "sum(Sig2)*0.9\n",
    "sum(Sig2[:2])\n",
    "sum(Sig2[:3])\n",
    "#前3个元素所包含的能量超过总能量的90%，故可以将这个11维的矩阵转换为3维"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the 0 and 3 similarity is: 0.490950\n",
      "the 0 and 5 similarity is: 0.484274\n",
      "the 0 and 10 similarity is: 0.512755\n",
      "the 1 and 3 similarity is: 0.491294\n",
      "the 1 and 5 similarity is: 0.481516\n",
      "the 1 and 10 similarity is: 0.509709\n",
      "the 2 and 3 similarity is: 0.491573\n",
      "the 2 and 5 similarity is: 0.482346\n",
      "the 2 and 10 similarity is: 0.510584\n",
      "the 4 and 3 similarity is: 0.450495\n",
      "the 4 and 5 similarity is: 0.506795\n",
      "the 4 and 10 similarity is: 0.512896\n",
      "the 6 and 3 similarity is: 0.743699\n",
      "the 6 and 5 similarity is: 0.468366\n",
      "the 6 and 10 similarity is: 0.439465\n",
      "the 7 and 3 similarity is: 0.482175\n",
      "the 7 and 5 similarity is: 0.494716\n",
      "the 7 and 10 similarity is: 0.524970\n",
      "the 8 and 3 similarity is: 0.491307\n",
      "the 8 and 5 similarity is: 0.491228\n",
      "the 8 and 10 similarity is: 0.520290\n",
      "the 9 and 3 similarity is: 0.522379\n",
      "the 9 and 5 similarity is: 0.496130\n",
      "the 9 and 10 similarity is: 0.493617\n",
      "the 0 and 3 similarity is: 0.341942\n",
      "the 0 and 5 similarity is: 0.124132\n",
      "the 0 and 10 similarity is: 0.116698\n",
      "the 1 and 3 similarity is: 0.345560\n",
      "the 1 and 5 similarity is: 0.126456\n",
      "the 1 and 10 similarity is: 0.118892\n",
      "the 2 and 3 similarity is: 0.345149\n",
      "the 2 and 5 similarity is: 0.126190\n",
      "the 2 and 10 similarity is: 0.118640\n",
      "the 4 and 3 similarity is: 0.450126\n",
      "the 4 and 5 similarity is: 0.528504\n",
      "the 4 and 10 similarity is: 0.544647\n",
      "the 6 and 3 similarity is: 0.923822\n",
      "the 6 and 5 similarity is: 0.724840\n",
      "the 6 and 10 similarity is: 0.710896\n",
      "the 7 and 3 similarity is: 0.319482\n",
      "the 7 and 5 similarity is: 0.118324\n",
      "the 7 and 10 similarity is: 0.113370\n",
      "the 8 and 3 similarity is: 0.334910\n",
      "the 8 and 5 similarity is: 0.119673\n",
      "the 8 and 10 similarity is: 0.112497\n",
      "the 9 and 3 similarity is: 0.566918\n",
      "the 9 and 5 similarity is: 0.590049\n",
      "the 9 and 10 similarity is: 0.602380\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(4, 3.3469521867021728), (9, 3.33537965732747), (6, 3.3071930278130375)]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## P264 基于SVD的评分估计\n",
    "#利用SVD将所有的菜肴映射到一个低维空间\n",
    "##reload(svdRec)\n",
    "## \n",
    "myMat = mat(loadExData2())\n",
    "recommend(myMat, 1, estMethod=svdEst)\n",
    "recommend(myMat, 1, estMethod=svdEst,simMeas=pearsSim)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "****original matrix******\n",
      "****reconstructed matrix using 2 singular values******\n"
     ]
    }
   ],
   "source": [
    "## P266 示例：基于SVD的图像压缩\n",
    "#原始图像为32×32=1024像素的图像，用SVD对其进行压缩，以节省空间或带宽开销\n",
    "##reload(svdRec)\n",
    "## \n",
    "imgCompress(2)\n",
    "#只需要两个奇异值就能相当精确地对图像实现重构，\n",
    "#U和VT都是32×2的矩阵，有两个奇异值，\n",
    "#也即只需要32×2+2+32×2=130个0、1进行存储。\n",
    "#原来需要1024个0、1，几乎获得10倍的压缩比"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
